﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace dst
{
    class SimplifySet
    {
        List<Exp> oriList;

        int totalXOR = 0;

        // 通过List的Count统计2子式出现的频度
        Dictionary<Exp, List<Exp>> riSub2 = new Dictionary<Exp, List<Exp>>();
        Dictionary<Exp, int> riSub2Count = new Dictionary<Exp, int>();

        Dictionary<Exp, List<Exp>> sub2 = new Dictionary<Exp, List<Exp>>();
        Dictionary<Exp, int> sub2Count = new Dictionary<Exp, int>();

        // 存放被替换的2子式列表
        public Dictionary<Exp, Exp> dicMap = new Dictionary<Exp, Exp>();

        // 存放oriList中每个元素被化简后的值
        public Dictionary<Exp, Exp> dicOri = new Dictionary<Exp, Exp>();

        int maxFreq = 0;
        Exp maxFExp = null;

        public SimplifySet()
        {
        }

        public int TotalXOR
        {
            get { return totalXOR; }
        }

        public void Add(List<Exp> list)
        {
            oriList = list;

            for (int i = 0; i < list.Count; i++)
            {
                if (!dicOri.ContainsKey(list[i]))
                    dicOri.Add(list[i], list[i]);
                Add(list[i]);
            }
        }

        public void Add(Exp e)
        {
            if (e is Ele)
                return;

            List<Exp> clo = e.GenClosure(2);
            if (!sub2.ContainsKey(e))
            {
                sub2.Add(e, clo);
                sub2Count.Add(e, 1);
            }
            else
                sub2Count[e]++;

            for (List<Exp>.Enumerator enu = clo.GetEnumerator(); enu.MoveNext(); )
            {
                if (!riSub2.ContainsKey(enu.Current))
                {
                    List<Exp> list = new List<Exp>();
                    list.Add(e);
                    riSub2.Add(enu.Current, list);
                    riSub2Count.Add(enu.Current, 1);
                }
                else
                {
                    if (!riSub2[enu.Current].Contains(e))
                        riSub2[enu.Current].Add(e);
                    riSub2Count[enu.Current]++;
                }

                if (maxFreq < riSub2Count[enu.Current])
                {
                    maxFreq = riSub2Count[enu.Current];
                    maxFExp = enu.Current;
                }
            }
        }

        public void Simplify()
        {
            //Exp[] subs = sub2.ToArray();
            int it = 0;
            while (maxFreq > 1) //化简的目的是让所有子式都只出现一次
            {
                Ele inter = Ele.GetEle("t", it++);
                dicMap.Add(maxFExp, inter);

                // 找到每个包含maxFExp的e
                int c = riSub2[maxFExp].Count;
                for (int i = 0; i < c; i++)
                {
                    Exp e = riSub2[maxFExp][0];
                    // 将每个e的2子式减去1次出现频率（从反查索引里删掉e）
                    for (int j = 0; j < sub2[e].Count; j++)
                    {
                        Exp tmpSub2 = sub2[e][j];
                        riSub2[tmpSub2].Remove(e);
                        riSub2Count[tmpSub2] -= sub2Count[e];
                        //for(int k = riSub2[tmpSub2].Count - 1; k >= 0; k--)
                        //    if(riSub2[tmpSub2][k] == e)
                        //        riSub2[tmpSub2].RemoveAt(k);

                        if (riSub2Count[tmpSub2] == 0)
                        {
                            riSub2.Remove(tmpSub2);
                            riSub2Count.Remove(tmpSub2);
                        }
                    }

                    // 将所有包含了maxFExp的e删掉
                    sub2.Remove(e);
                    
                    Exp newE = e.Replace(maxFExp, inter);
                    Add(newE);

                    Exp ori = dicOri[e];
                    dicOri.Remove(e);
                    dicOri.Add(newE, ori);
                }

                riSub2.Remove(maxFExp);

                // 获得更新的maxFExp
                maxFreq = 0;
                for (Dictionary<Exp, int>.Enumerator enu = riSub2Count.GetEnumerator(); enu.MoveNext(); )
                {
                    if (enu.Current.Value > maxFreq)
                    {
                        maxFreq = enu.Current.Value;
                        maxFExp = enu.Current.Key;
                    }
                }
            }
        } //end of Simplify()

        public string Output()
        {
            StringBuilder sb = new StringBuilder();
            totalXOR = 0;
            Dictionary<Exp, Exp> revOri = new Dictionary<Exp, Exp>();
            for (Dictionary<Exp, Exp>.Enumerator enu = dicOri.GetEnumerator(); enu.MoveNext(); )
                revOri.Add(enu.Current.Value, enu.Current.Key);

            for (int i = 0; i < oriList.Count; i++)
            {
                if (revOri[oriList[i]] is AddExp<Exp>)
                    totalXOR += ((AddExp<Exp>)revOri[oriList[i]]).Count - 1;
                sb.Append(revOri[oriList[i]] + ",");
            }
            sb.Append("\n");
            for (Dictionary<Exp, Exp>.Enumerator enu = dicMap.GetEnumerator(); enu.MoveNext(); )
            {
                if(enu.Current.Key is AddExp<Exp>)
                    totalXOR += ((AddExp<Exp>)enu.Current.Key).Count - 1;
                sb.Append(enu.Current.Value + "=" + enu.Current.Key + ",");
            }

            return sb.ToString();
        } //end of Output()
    }
}
